# coding: utf-8

import sys
sys.path.append('../3_data_structure')
from stack import Stack

parentheses1 = '(({}[]))'
parentheses2 = '((({)})[])'


def check_balanced_symbols(input_string):
    stack = Stack()

    pair = {')': '(', '}': '{', ']': '['}

    left = pair.values()
    right = pair.keys()

    for item in input_string:
        if item in left:
            stack.push(item)
        elif item in right:
            if stack.is_empty():
                return False
            else:
                top = stack.pop()
                if top != pair[item]:
                    return False

    return stack.is_empty()


print(check_balanced_symbols(parentheses1))
print(check_balanced_symbols(parentheses2))
